Міністерство Освіти України
Національний університет "Львівська політехніка"
М Е Т О Д И Ч Н А В К А З І В К А
До лабораторної роботи № 6
На тему: “ Методи сортування. Злиття.”
з дисципліни
" Алгоритми і структури даних"
Для базового напрямку 6.0804 "Комп’ютерні науки"
ЗАТВЕРДЖЕНО
на засіданні кафедри
програмного забезпечення
протокол № від 2007 р.
Львів – 2007
Методичні вказівки до лабораторних робіти з дисципліни " Алгоритми і структури даних" Для базового напрямку 6.0804 "Комп’ютерні науки"
Укладач: Коротєєва Т. О.
Вовчак І. Г.
Відповідальний за випуск:
Рецензенти:
Тема роботи: Ознайомлення із методами сортування. Зокрема із методом злиття.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із цифровим методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу Шелла.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Ключ, по якому відбувається сортування, необхідно розділити на частини, розряди ключа. Наприклад, слово можна розділити по буквах, число - по цифрах...
До сортування необхідно знати два параметри: до і m, де
к - кількість розрядів в щонайдовшому ключі
m - розрядність даних: кількість можливих значень розряду ключа
При сортуванні українських слів m = 33, оскільки буква може приймати не більше 33 значень. Якщо в щонайдовшому слові 10 букв, до = 10.
Аналогічно, для шістнадцяткових чисел m=16, якщо як розряд брати цифру, і m=256, якщо використовувати побайтове ділення.
Ці параметри не можна змінювати в процесі роботи алгоритму. У цьому - ще одна відмінність методу від вищеописаних.
Сортування масивів
Нехай в нас є масив source з n десяткових цифр ( m = 10 ).
Наприклад, source[7]= { 7, 9, 8, 5, 4, 7, 7 }, n=7. Тут покладемо const k=1.
Створити масив count з m елементів(лічильників).
Привласнити count[i] кількість елементів source, рівних i. Для цього:
проинициализовать count[] нулями
пройти по source від початку до кінця, для кожного числа збільшуючи елемент count з відповідним номером.
for( i=0; i<n; i++) count [ source[i]]++
У нашому прикладі count[] = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }
Привласнити count[i] значення, рівне сумі всіх елементів до даного: count[i]= count[0]+count[1]+...count[i-1]. У нашому прикладі count[] = { 0, 0, 0, 0, 1, 2, 2, 2, 5, 6 }Ця сума є кількістю чисел початкового масиву, менших i.
Провести остаточну розстановку.
Для кожного числа source[i] ми знаємо, скільки чисел менше його - це значення зберігається в count[ source[i]]. Таким чином, нам відоме остаточне місце числа у впорядкованому масиві: якщо є K чисел менше даного, то воно повинне стояти на на позиції K+1. Здійснюємо прохід по масиву source зліва направо, одночасно заповнюючи вихідний масив dest:
for ( i=0; i<n; i++ ) {
з = source[i];
dest[ count[c]]= з;
count[c]++; // для чисел, що повторюються
}
Таким чином, число c=source[i] ставиться на місце count[c]. На цей випадок, якщо числа повторюються в масиві, передбачений оператор count[c]++, який збільшує значення позиції для наступного числа з, якщо таке буде.
Цикли займають (n + m) часу. Стільки ж вимагається пам'яті.
Отже, ми навчилися за (n + m) сортувати цифри. А від цифр до рядків і чисел - 1 крок. Хай у нас в кожному ключі до цифр ( m = 10 ). Аналогічно злучаю із списками відсортуємо їх в декілька проходів від молодшого розряду до старшого.
Загальна кількість операцій, таким чином, ( до(n+m)), при використовуваній додатково пам'яті (n+m).
Реалізація програми:
// Функція для останнього проходу при порозрядному сортуванні чисел з плаваючою крапкою
template<class T>
void floatRadixLastPass (short Offset, long N, T *source, T *dest, long *count) {
T *sp;
long s, з, i *cp;
uchar *bp;
long numNeg=0;
for(i=128;i<256;i++) numNeg += count[i];
s=numNeg;
cp = count;
for (i = 0; i < 128; ++i, ++cp) {
з = *cp;
*cp = s;
s += з;
// зміни, що стосуються зворотного розташу...
